package com.person.leetcode.editor.cn;

import java.util.*;

/**
  * 17.电话号码的字母组合
  * 2022-06-10 15:27:06
**/
public class Sequence_0017_LetterCombinationsOfAPhoneNumber {
    public static void main(String[] args) {
        Solution solution = new Sequence_0017_LetterCombinationsOfAPhoneNumber().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
//class Solution {
////          2   3  4   5   6   7    8   9
////        abc def ghi jkl mno pqrs tuv wxyz
//        private static final String[][] map = {{"a","b","c"},{"d","e","f"},{"g","h","i"},{"j","k","l"},
//        {"m","n","o"},{"p","q","r","s"},{"t","u","v"},{"w","x","y","z"}};
//    public List<String> letterCombinations(String digits) {
//        List<String[]> comb = new ArrayList<String[]>();
//        for (int i = 0; i < digits.length(); i++) {
//            comb.add(map[digits.charAt(i) - '0']) ;
//        }
//        return combination(comb);
//    }
//
//    public List combination(List<String[]> comb){
//        for (int i = 0; i < comb.size(); i++) {
//        }
//        return null;
//    }
//}

    //tmd自己怎么没想到 递归啊
    class Solution {
        public List<String> letterCombinations(String digits) {
            List<String> combinations = new ArrayList<String>();
            if (digits.length() == 0) {
                return combinations;
            }
            Map<Character, String> phoneMap = new HashMap<Character, String>() {{
                put('2', "abc");
                put('3', "def");
                put('4', "ghi");
                put('5', "jkl");
                put('6', "mno");
                put('7', "pqrs");
                put('8', "tuv");
                put('9', "wxyz");
            }};
            backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
            return combinations;
        }

        public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits, int index, StringBuffer combination) {
            if (index == digits.length()) {
                combinations.add(combination.toString());
            } else {
                char digit = digits.charAt(index);
                String letters = phoneMap.get(digit);
                int lettersCount = letters.length();
                for (int i = 0; i < lettersCount; i++) {
                    combination.append(letters.charAt(i));
                    backtrack(combinations, phoneMap, digits, index + 1, combination);
                    combination.deleteCharAt(index);
                }
            }
        }
    }

//leetcode submit region end(Prohibit modification and deletion)

}